#include <stdlib.h>
#include <stdio.h>
typedef struct node{
    int val;
    struct node* left;
    struct node* right;
}BSTreeNode, *BSTree;


void insert(BSTree &root, int val){
    if(root == NULL){
        root = (BSTree) malloc(sizeof(BSTreeNode));
        *root = {val, NULL, NULL};
        return;
    }
    if(val >= root->val){
        insert(root->right, val);
    }else{
        insert(root->left, val);
    } 
}
void insertIter(BSTree &root, int val){
    if(root == NULL){
        root = (BSTree) malloc(sizeof(BSTreeNode));
        *root = {val, NULL, NULL};
        return;
    }
    BSTree p = root;
    while(p != NULL){
        if(val >= p->val){
            if(p->right)
                p = p->right;
            else 
                break;
        }else{
            if(p->left)
                p = p->left;
            else
                break;
        }
    }
    if(val >= p->val){
        p->right = (BSTree) malloc(sizeof(BSTreeNode));
        *(p->right) = {val, NULL, NULL};
    }else{
        p->left = (BSTree) malloc(sizeof(BSTreeNode));
        *(p->left) = {val, NULL, NULL};
    }
}
void inorder(BSTree root){
    if(root == NULL){
        return;
    }
    inorder(root->left);
    printf("%d\t", root->val);
    inorder(root->right);
}
